package com.yanceysong.codetop.s71_s80;

import com.yanceysong.common.TreeNode;


public class S78_Easy_543_二叉树的直径 {

    /**
     * .S78_Easy_543_二叉树的直径
     * <p>
     * .链接：<a href="https://leetcode.cn/problems/diameter-of-binary-tree/">https://leetcode.cn/problems/diameter-of-binary-tree/</a>
     * <p>
     * .题目：给你一棵二叉树的根节点，返回该树的「直径」。
     * .定义：二叉树的直径是任意两个节点之间最长路径的长度（按边数计）。该路径可能经过也可能不经过根节点。
     * <p>
     * .核心标签：二叉树 / 深度优先搜索 / 后序遍历 / 递归 / 直径
     * <p>
     * .示例：
     * .1) 输入：root = [1,2,3,4,5]
     * .   ASCII：
     * .          1
     * .         / \\
     * .        2   3
     * .       / \\
     * .      4   5
     * .   输出：3
     * .   解释：最长路径可以是 4 → 2 → 1 → 3，边数为 3。
     * <p>
     * .2) 输入：root = [1]
     * .   输出：0 （只有一个节点，没有边）
     * <p>
     * .解题思路：
     * .- 直径的本质是在每个节点处尝试“穿过该节点”的路径长度：左子树深度 + 右子树深度。
     * .- 在一次后序遍历中，递归返回“以该节点为根的子树的最大深度”（按节点数或边数均可，但要统一口径）。
     * .- 同时在全局维护当前遇到的最长路径长度。
     * .- 本实现将深度按“节点数”返回，并维护最长路径的“节点数”，最终将其转换为“边数”。
     * <p>
     * .复杂度分析：
     * .- 时间复杂度：O(n)，n 为节点数，每个节点仅访问一次。
     * .- 空间复杂度：O(h)，h 为树高，递归栈深度；最坏 O(n)，平均 O(log n)。
     * <p>
     * .关键洞察：
     * .- 直径不一定经过根节点，需对所有节点都计算一次“左深度 + 右深度”。
     * .- 递归返回值（深度）与全局答案（最长路径）要分工明确：返回值用于父节点计算，全局用于记录最佳结果。
     * .- 统一“节点数/边数”的口径，避免 off-by-one 错误。本解将最长路径以“节点数”维护，最终直径=节点数-1。
     */
    // 记录遍历过程中遇到的最长路径上的节点数（而非边数）
    private int maxNodesOnLongestPath = 1;

    public int diameterOfBinaryTree(TreeNode root) {
        // 空树的直径为 0
        if (root == null) {
            return 0;
        }

        // 递归计算每个节点的子树深度，同时更新全局最长路径
        computeDepthFromNode(root);

        // 直径是最长路径的边数 = 节点数 - 1
        return maxNodesOnLongestPath - 1;
    }

    /**
     * .计算“以当前节点为根的子树的最大深度”（以节点数计），并在过程中更新全局最长路径。
     * .后序遍历：先拿到左右子树的深度，再用它们更新经过当前节点的路径长度。
     * <p>
     * .@param node 当前节点
     * .@return 该节点为根的子树最大深度（节点数）
     */
    private int computeDepthFromNode(TreeNode node) {
        if (node == null) {
            return 0; // 空节点深度为 0
        }
        // 递归获取左右子树的最大深度（节点数）
        int leftDepthInNodes = computeDepthFromNode(node.left);
        int rightDepthInNodes = computeDepthFromNode(node.right);

        // 经过当前节点的最长路径节点数 = 左深度 + 右深度 + 1（当前节点）
        int nodesOnPathThroughThis = leftDepthInNodes + rightDepthInNodes + 1;

        // 更新全局最长路径
        maxNodesOnLongestPath = Math.max(maxNodesOnLongestPath, nodesOnPathThroughThis);

        // 返回“该节点为根的子树最大深度”（节点数）
        return Math.max(leftDepthInNodes, rightDepthInNodes) + 1;
    }

    /**
     * .示例与测试：尽量覆盖典型与边界场景。
     */
    public static void main(String[] args) {
        S78_Easy_543_二叉树的直径 solver = new S78_Easy_543_二叉树的直径();
        System.out.println("=== 二叉树直径测试开始 ===");

        // 测试1：题目示例 [1,2,3,4,5]
        System.out.println("\n--- 测试1：示例树 [1,2,3,4,5] ---");
        TreeNode t1 = new TreeNode(1);
        t1.left = new TreeNode(2);
        t1.right = new TreeNode(3);
        t1.left.left = new TreeNode(4);
        t1.left.right = new TreeNode(5);
        System.out.println("结构：\n       1\n      / \\\n     2   3\n    / \\\n   4   5");
        int d1 = solver.diameterOfBinaryTree(t1);
        System.out.println("diameter = " + d1 + " (期望：3)");
        assert d1 == 3;

        // 测试2：单节点树
        System.out.println("\n--- 测试2：单节点 ---");
        TreeNode t2 = new TreeNode(42);
        int d2 = solver.diameterOfBinaryTree(t2);
        System.out.println("diameter = " + d2 + " (期望：0)");
        assert d2 == 0;

        // 测试3：空树
        System.out.println("\n--- 测试3：空树 ---");
        TreeNode t3 = null;
        int d3 = solver.diameterOfBinaryTree(t3);
        System.out.println("diameter = " + d3 + " (期望：0)");
        assert d3 == 0;

        // 测试4：左斜链（直径为链长-1）
        System.out.println("\n--- 测试4：左斜链 ---");
        TreeNode t4 = new TreeNode(1);
        t4.left = new TreeNode(2);
        t4.left.left = new TreeNode(3);
        t4.left.left.left = new TreeNode(4);
        int d4 = solver.diameterOfBinaryTree(t4);
        System.out.println("diameter = " + d4 + " (期望：3)");
        assert d4 == 3;

        // 测试5：右斜链（直径为链长-1）
        System.out.println("\n--- 测试5：右斜链 ---");
        TreeNode t5 = new TreeNode(1);
        t5.right = new TreeNode(2);
        t5.right.right = new TreeNode(3);
        t5.right.right.right = new TreeNode(4);
        int d5 = solver.diameterOfBinaryTree(t5);
        System.out.println("diameter = " + d5 + " (期望：3)");
        assert d5 == 3;

        // 测试6：直径不经过根节点
        System.out.println("\n--- 测试6：直径不经过根 ---");
        TreeNode t6 = new TreeNode(1);
        t6.left = new TreeNode(2);
        t6.left.left = new TreeNode(3);
        t6.left.left.left = new TreeNode(4);
        t6.left.right = new TreeNode(5);
        // 最长路径 4 → 3 → 2 → 5，边数 3
        int d6 = solver.diameterOfBinaryTree(t6);
        System.out.println("diameter = " + d6 + " (期望：3)");
        assert d6 == 3;

        // 测试7：更复杂的平衡树
        System.out.println("\n--- 测试7：平衡树 ---");
        TreeNode t7 = new TreeNode(10);
        t7.left = new TreeNode(6);
        t7.right = new TreeNode(14);
        t7.left.left = new TreeNode(4);
        t7.left.right = new TreeNode(8);
        t7.right.left = new TreeNode(12);
        t7.right.right = new TreeNode(16);
        // 例如路径 4 → 6 → 10 → 14 → 16，边数为 4
        int d7 = solver.diameterOfBinaryTree(t7);
        System.out.println("diameter = " + d7 + " (期望：4)");
        assert d7 == 4;

        System.out.println("\n=== 所有测试完成 ===");
    }
}
